package com.yvon.service.demo.algorithm.offer;

/**
 * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9815.%20%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B8%AD1%E7%9A%84%E4%B8%AA%E6%95%B0/README
 *
 */
public class P15 {
    public static void main(String[] args) {
        Solution solution = new P15().new Solution();
        int i = solution.hammingWeight(00000000000000000000000001011011);
        System.out.println(i);
    }

    /**
     * 1 & 1 = 1
     * 0 & 1 = 0
     *
     * 我们可以对每次得到的n对1进行按位与，这样的话如果得到n最后一位为1时其结果也会得到1，而当n最后一位为0时发现不会得到1.然后每次对n除以2，也就是右移1位即可
     * 即每次直接判断二进制最低位的数是不是1。
     */
    class Solution {

        public int hammingWeight(int n) {
            int ans = 0;
            while (n != 0) {
                ans += n & 1;
                n = n>>1;
            }
            return ans;
        }

        /**
         * n=n&(n-1) : 将最后一位1变成0
         */
        public int hammingWeight1(int n) {
            int ans = 0;
            while (n != 0) {
                n &= n -1;
                ++ ans;
            }
            return ans;
        }
    }
}
